//274. H 指数
//思路：计数排序
//当元素大于个数时，让大于等于个数的元素计数在n位置
//逆序遍历计数数组，当total >= i时，就说明该数字为 H指数


#include <vector>
using namespace std;

class Solution
{
public:
    int hIndex(vector<int>& citations)
    {
        int n = citations.size();
        vector<int> v(n+1);
        for(int i = 0; i < n; i++)
        {
            if(citations[i] >= n) v[n]++;
            else v[citations[i]]++; 
        }

        int total = 0;
        for(int i = n; i >= 0; i--)
        {
            total += v[i];
            if(total >= i) return i;//此时就算走到了中间位置
        }
        
        return 0;
    }
};